Arbre B

Arbre B

Exemple d'un 3-5 B-arbre

Découvreurs ou inventeurs	Rudolf Bayer, Edward M. McCreight
Date de découverte	1972[1]
Problème lié	Structure de données
Structure des données	Arbre enraciné

Complexité en temps

Pire cas	${\displaystyle O(\log n)(insertion)}$, ${\displaystyle O(\log n)(suppression)}$, ${\displaystyle O(\log n)(recherche)}$
Moyenne	${\displaystyle O(\log n)}$, ${\displaystyle O(\log n)}$, ${\displaystyle O(\log n)}$

Complexité en espace

Pire cas	${\displaystyle O(n)}$
Moyenne	${\displaystyle O(n)}$

modifier - modifier le code - modifier Wikidata

En informatique, un arbre B (appelé aussi B-arbre par analogie au terme anglais « B-tree ») est une structure de données en arbre équilibré. Les arbres B sont principalement mis en œuvre dans les mécanismes de gestion de bases de données et de systèmes de fichiers. Ils stockent les données sous une forme triée et permettent une exécution des opérations d'insertion et de suppression en temps toujours logarithmique.

Le principe est de permettre aux nœuds parents de posséder plus de deux nœuds enfants : c'est une généralisation de l’arbre binaire de recherche. Ce principe minimise la taille de l'arbre et réduit le nombre d'opérations d'équilibrage. De plus un arbre B grandit à partir de la racine, contrairement à un arbre binaire de recherche qui croît à partir des feuilles.

Le créateur des arbres B, Rudolf Bayer, n'a pas explicité la signification du « B ». L'explication la plus fréquente est que le B correspond au terme anglais « balanced » (en français : « équilibré »). Cependant, il pourrait aussi découler de « Bayer », du nom du créateur, ou de « Boeing », du nom de la firme pour laquelle le créateur travaillait (Boeing Scientific Research Labs).